package com.hsc.sort;

import java.util.Arrays;

/**
 * @author hsc
 * @date 2024-03-28
 * @Description
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 11, 8, 6, 9, 10, 12, 1, 20, 13}; // 待排序的数组
        BubbleSort(array);
    }

    /**
     * 冒泡排序：
     * 排序的本质：
     * 第一步是比较，
     * 第二步是换位置
     */
    private static void BubbleSort(int[] array) {
        // 确定临界值
        if (array == null || array.length < 2) {
            return;
        }
        int length = array.length;
        // 外层循环 控制比较的次数
        for (int i = 0; i < length - 1; i++) {
            // 内层进行每次比较交换 每次回冒出最大的一个数值
            // 每一轮比较会确定一个最大值的位置 所以可以对数组进行优化 需要比较的次数减少
            // 里面循环做的事情：相邻的元素进行比较交换
            // 第1次遍历：
            //比较 5 和 11：不交换 → [5, 11, 8, 6, 9, 10, 12, 1, 20, 13]
            //比较 11 和 8：交换 → [5, 8, 11, 6, 9, 10, 12, 1, 20, 13]
            //比较 11 和 6：交换 → [5, 8, 6, 11, 9, 10, 12, 1, 20, 13]
            //比较 11 和 9：交换 → [5, 8, 6, 9, 11, 10, 12, 1, 20, 13]
            //比较 11 和 10：交换 → [5, 8, 6, 9, 10, 11, 12, 1, 20, 13]
            //比较 12 和 1：交换 → [5, 8, 6, 9, 10, 11, 1, 12, 20, 13]
            //比较 20 和 13：交换 → [5, 8, 6, 9, 10, 11, 1, 12, 13, 20]
            //结果：[5, 8, 6, 9, 10, 11, 1, 12, 13, 20]
            for (int j = 0; j < length - 1 - i; j++) {
                // 比较
                if (array[j] > array[j + 1]) {
                    // 对数组的元素进行交换
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                // j递增
            }


//             输出第一次遍历的结果
            System.out.println("第" + i + "次比较交换结果为：" + Arrays.toString(array));
            //第0次比较交换结果为：[5, 8, 6, 9, 10, 11, 1, 12, 13, 20]
            //第1次比较交换结果为：[5, 6, 8, 9, 10, 1, 11, 12, 13, 20]
            //第2次比较交换结果为：[5, 6, 8, 9, 1, 10, 11, 12, 13, 20]
            //第3次比较交换结果为：[5, 6, 8, 1, 9, 10, 11, 12, 13, 20]
            //第4次比较交换结果为：[5, 6, 1, 8, 9, 10, 11, 12, 13, 20]
            //第5次比较交换结果为：[5, 1, 6, 8, 9, 10, 11, 12, 13, 20]
            //第6次比较交换结果为：[1, 5, 6, 8, 9, 10, 11, 12, 13, 20]
            //第7次比较交换结果为：[1, 5, 6, 8, 9, 10, 11, 12, 13, 20]
            //第8次比较交换结果为：[1, 5, 6, 8, 9, 10, 11, 12, 13, 20]

            // 如果进行降序排序呢
//            for (int j = 0; j < length - 1; j++) {
                // 比较交换过程
                // 第1次遍历：原始数组为：[5, 11, 8, 6, 9, 10, 12, 1, 20, 13]
                //j=0:比较 11 和 5：11比5大 ->交换 → [11, 5, 8, 6, 9, 10, 12, 1, 20, 13]
                //j=1比较 8 和 5：8比5大->交换 → [11, 8, 5, 6, 9, 10, 12, 1, 20, 13]
                //j=2比较 6 和 5：6比5大->交换 → [11, 8, 6, 5, 9, 10, 12, 1, 20, 13]
                //j=3比较 9 和 5：9比5大->换 → [11, 8, 6, 9, 5, 10, 12, 1, 20, 13]
                //j=4比较 10 和 5：10比5大->交换 → [11, 8, 6, 9, 10, 5, 12, 1, 20, 13]
                //j=5比较 12 和 5：12比5大->交换 → [11, 8, 6, 9, 10, 12, 5, 1, 20, 13]
                //j=6比较 1 和 5：1比5小不交换 → [11, 8, 6, 9, 10, 12, 5, 1, 20, 13]
                //j=7比较 20 和 1：20比1大交换 → [11, 8, 6, 9, 10, 12, 5, 20, 1, 13]
                //j=8比较 13 和 1：13比1大交换 → [11, 8, 6, 9, 10, 12, 5, 20, 13, 1]
                // 所有内层的每一次循环会得到一个最小值进行冒出来
//                if (array[j + 1] > array[j]) {
//                    int temp = array[j];
//                    array[j] = array[j + 1];
//                    array[j + 1] = temp;
//                }
//            }
//            System.out.println("第" + i + "次比较交换结果为：" + Arrays.toString(array));
            //第0次比较交换结果为：[11, 8, 6, 9, 10, 12, 5, 20, 13, 1]
            //第1次比较交换结果为：[11, 8, 9, 10, 12, 6, 20, 13, 5, 1]
            //第2次比较交换结果为：[11, 9, 10, 12, 8, 20, 13, 6, 5, 1]
            //第3次比较交换结果为：[11, 10, 12, 9, 20, 13, 8, 6, 5, 1]
            //第4次比较交换结果为：[11, 12, 10, 20, 13, 9, 8, 6, 5, 1]
            //第5次比较交换结果为：[12, 11, 20, 13, 10, 9, 8, 6, 5, 1]
            //第6次比较交换结果为：[12, 20, 13, 11, 10, 9, 8, 6, 5, 1]
            //第7次比较交换结果为：[20, 13, 12, 11, 10, 9, 8, 6, 5, 1]
            //第8次比较交换结果为：[20, 13, 12, 11, 10, 9, 8, 6, 5, 1]

        }

        // 打印排序后的数组
        System.out.print("排序后的数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }


    }
}
